package data_structures_and_algorithms.tree.traverse.classic;

import common.TreeNode;
import sun.reflect.generics.tree.Tree;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName PostTraverse
 * @Description: 后序遍历：
 * @Author: yongliang.ma
 * @Create_time:2022/10/16 15:53
 */
public class PostTraverse {


    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);

        node3.right = node2;
        node2.right= node1;
        List<Integer> integers = new PostTraverse().postTraverse(node3);
        System.out.println(Arrays.toString(integers.toArray()));
    }

    public List<Integer> postTraverse(TreeNode root){
        postTraverseLoop(root);
        return list;
    }

    List<Integer> list = new LinkedList<>();
    public void postTraverseCur(TreeNode treeNode){
        if (treeNode == null)
            return;
        postTraverseCur(treeNode.left);
        postTraverseCur(treeNode.right);
        list.add(treeNode.val);
    }

    public void postTraverseLoop(TreeNode treeNode){
        if (treeNode == null)
            return;

        TreeNode node = treeNode, pre = null;// 创建pre记录上一个打印的节点，
        Deque<TreeNode> deque = new LinkedList<>();

        while (node != null || !deque.isEmpty()){
            while (node != null){
                deque.push(node);
                node = node.left;
            }

            node = deque.pop();
            if (node.right == null || node.right == pre){
                list.add(node.val);
                pre = node;
                node = null;
            }else {
                deque.push(node);
                node = node.right;
            }
        }
    }

    // 非常容易理解
    public class ZuoGodVersion{

        public List<Integer> postTraverseLoop(TreeNode root){
            if (root == null)
                return list;
            Deque<TreeNode> deque = new LinkedList<>();
            deque.push(root);
            // pre定义：上一次处理的节点，初始赋值可以创建节点 但是不可以为null
            TreeNode pre = root, cur = null;
            while (!deque.isEmpty()){
                cur = deque.peek();
                // 判断左孩子是否已经被处理，两种情况1、上次打印的位置为左孩子节点，2、上次打印的位置为右孩子节点（这种情况下 左孩子也是被处理的）
                if (cur.left != null && pre != cur.left && pre != cur.right){
                    deque.push(cur.left);
                // 判断右孩子是否已经被处理，右孩子是否为上次打印的节点
                }else if (cur.right != null && pre != cur.right){
                    deque.push(cur.right);
                }else {
                    // 弹出打印
                    list.add(deque.pop().val);
                    pre = cur;
                }
            }
            return list;
        }
    }

}
